import numpy as np
import time

def find_same_elements(board):
    non_zero_elements = np.unique(board[board != 0])
    same_elements_positions = {}
    for element in non_zero_elements:
        positions = list(zip(*np.where(board == element)))
        if len(positions) > 1:
            same_elements_positions[element] = positions
    return same_elements_positions

def eliminate_same_elements(board):
    same_elements_positions = find_same_elements(board)
    eliminated = False
    already_eliminated = set()  
    elimination_coords = [] 

    for element, positions in same_elements_positions.items():
        if len(positions) > 1:
            for i in range(len(positions)):
                for j in range(i+1, len(positions)):
                    pos1 = positions[i]
                    pos2 = positions[j]
                    if pos1 in already_eliminated or pos2 in already_eliminated:
                        continue

                    if pos1[0] == pos2[0] and np.all(board[pos1[0], min(pos1[1], pos2[1])+1:max(pos1[1], pos2[1])] == 0):
                        board[pos1], board[pos2] = 0, 0
                        eliminated = True
                        already_eliminated.update([pos1, pos2])
                        elimination_coords.append(pos1) 
                        elimination_coords.append(pos2)
                        break
                    elif pos1[1] == pos2[1] and np.all(board[min(pos1[0], pos2[0])+1:max(pos1[0], pos2[0]), pos1[1]] == 0):
                        board[pos1], board[pos2] = 0, 0
                        eliminated = True
                        already_eliminated.update([pos1, pos2])
                        elimination_coords.append(pos1)
                        elimination_coords.append(pos2)
                        break
    return eliminated, board, elimination_coords


def eliminate_elements_around(board, end_pos):
    eliminated = False
    rows, cols = board.shape
    element = board[end_pos]

    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # 右，左，下，上
    for dr, dc in directions:
        r, c = end_pos[0] + dr, end_pos[1] + dc

        if 0 <= r < rows and 0 <= c < cols:
            if board[r, c] == element:
                board[end_pos] = board[r, c] = 0
                eliminated = True
                break

    if not eliminated:
        for dr, dc in directions:
            r, c = end_pos[0] + dr, end_pos[1] + dc
            while 0 <= r < rows and 0 <= c < cols:
                if board[r, c] != 0:
                    if board[r, c] == element and \
                       np.all(board[min(end_pos[0], r)+1:max(end_pos[0], r), c] == 0) and \
                       np.all(board[r, min(end_pos[1], c)+1:max(end_pos[1], c)] == 0):
                        board[end_pos] = board[r, c] = 0
                        eliminated = True
                    break
                r += dr
                c += dc

    return eliminated, board


def path_is_clear(board, start_x, start_y, end_x, end_y):
    if start_x == end_x: 
        for y in range(min(start_y, end_y) + 1, max(start_y, end_y)):
            if board[start_x][y] != 0:
                return False
    elif start_y == end_y:
        for x in range(min(start_x, end_x) + 1, max(start_x, end_x)):
            if board[x][start_y] != 0:
                return False
    return True


def find_positions_and_intersections(board):
    elements = set(board.flatten()) - {0}
    for element in elements:
        positions = list(zip(*np.where(board == element)))
        intersections = set((x, y) for x in set(px for px, _ in positions)
                            for y in set(py for _, py in positions)) - set(positions)
        print(f"元素 {element} 的位置: {positions}")
        print(f"元素 {element} 的潜在交汇点: {intersections}")


def calculate_move_direction(start_pos, end_pos):
    if start_pos[0] == end_pos[0]:  
        if start_pos[1] < end_pos[1]:
            return 'right'
        else:
            return 'left'
    elif start_pos[1] == end_pos[1]: 
        if start_pos[0] < end_pos[0]:
            return 'down'
        else:
            return 'up'
    else:
        return None


def is_valid_intersection(board, element_x, element_y, intersection_x, intersection_y):
    if abs(intersection_x - element_x) + abs(intersection_y - element_y) == 1:
        return True

    if element_x == intersection_x:  
        return np.all(board[element_x, min(element_y, intersection_y)+1:max(element_y, intersection_y)] == 0)
    if element_y == intersection_y: 
        return np.all(board[min(element_x, intersection_x)+1:max(element_x, intersection_x), element_y] == 0)

    return False


def check_if_elements_can_move(board):
    rows, cols = board.shape
    can_move_elements = []

    for element_1_x in range(rows):
        for element_1_y in range(cols):
            element_1 = board[element_1_x][element_1_y]
            if element_1 != 0:
                for element_2_x in range(rows):
                    for element_2_y in range(cols):
                        element_2 = board[element_2_x][element_2_y]
                        if element_2 != 0 and element_1 == element_2 and \
                           element_1_x != element_2_x and element_1_y != element_2_y:
                            intersections = [
                                (element_1_x, element_2_y),
                                (element_2_x, element_1_y)
                            ]
                            for intersection in intersections:
                                intersection_x, intersection_y = intersection

                                if is_valid_intersection(board, element_1_x, element_1_y, intersection_x, intersection_y) or \
                                   is_valid_intersection(board, element_2_x, element_2_y, intersection_x, intersection_y):

                                    steps_to_intersection = abs(
                                        element_1_x - intersection_x) + abs(element_1_y - intersection_y)
                                    # print(
                                    # f"元素 {element_1} 在 ({element_1_x}, {element_1_y}) 和 ({element_2_x}, {element_2_y}) 可以移动到交汇点 ({intersection_x}, {intersection_y}), 移动步数: {steps_to_intersection}")

                                    can_move_elements.append((
                                        element_1,
                                        (element_1_x, element_1_y),
                                        (element_2_x, element_2_y),
                                        (intersection_x, intersection_y),
                                        steps_to_intersection  
                                    ))
    return can_move_elements 


def move_group_by_steps(board, top_left_row, top_left_col, direction, steps, is_column):
    max_rows, max_cols = board.shape  

    if board[top_left_row, top_left_col] == 0:
        return False

    width, height = 1, 1
    if is_column:
        if direction == 'up':
            while top_left_row > 0 and board[top_left_row - 1, top_left_col] != 0:
                top_left_row -= 1
                height += 1
        elif direction == 'down':
            while top_left_row + height < max_rows and board[top_left_row + height, top_left_col] != 0:
                height += 1
    else:
        if direction == 'left':
            while top_left_col > 0 and board[top_left_row, top_left_col - 1] != 0:
                top_left_col -= 1
                width += 1
        elif direction == 'right':
            while top_left_col + width < max_cols and board[top_left_row, top_left_col + width] != 0:
                width += 1

    # print("选定的矩形元素:")
    # for r in range(height):
        # for c in range(width):
            #print(board[top_left_row + r, top_left_col + c], end=' ')
        # print()  # 换行

    if direction == 'right':
        if top_left_col + width + steps > max_cols: 
            return False
        for row in range(top_left_row, top_left_row + height):
            for col in range(top_left_col + width, top_left_col + width + steps):
                if board[row][col] != 0:
                    return False
    elif direction == 'left':
        if top_left_col - steps < 0: 
            return False
        for row in range(top_left_row, top_left_row + height):
            for col in range(top_left_col - steps, top_left_col):
                if board[row][col] != 0: 
                    return False
    elif direction == 'down':
        if top_left_row + height + steps > max_rows:  
            return False
        for row in range(top_left_row + height, top_left_row + height + steps):
            for col in range(top_left_col, top_left_col + width):
                if board[row][col] != 0:  
                    return False
    elif direction == 'up':
        if top_left_row - steps < 0: 
            return False
        for row in range(top_left_row - steps, top_left_row):
            for col in range(top_left_col, top_left_col + width):
                if board[row][col] != 0: 
                    return False

    delta_row = steps if direction == 'down' else -steps if direction == 'up' else 0
    delta_col = steps if direction == 'right' else - \
        steps if direction == 'left' else 0
    new_top_left_row = top_left_row + delta_row
    new_top_left_col = top_left_col + delta_col
    temp_area = np.zeros((height, width), dtype=board.dtype)

    for r in range(height):
        for c in range(width):
            temp_area[r, c] = board[top_left_row + r, top_left_col + c]
            board[top_left_row + r, top_left_col + c] = 0

    for r in range(height):
        for c in range(width):
            board[new_top_left_row + r, new_top_left_col + c] = temp_area[r, c]

    return True  


def is_board_empty(board):
    return np.all(board == 0)


def save_path_to_file(file_path, move_path):
    with open(file_path, 'w') as file:
        for move in move_path:
            file.write(f"{move}\n")


def test_board_elimination_inverse(file_path='numbers.txt', output_file='move_path.txt', time_limit=30):
    start_time = time.time()
    board = np.loadtxt(file_path, dtype=int)

    print("初始棋盘:")
    print(board)

    move_path = []
    result = False

    def backtrack(board, move_path, start_time, time_limit, result):
        if time.time() - start_time > time_limit:
            print("已超时")
            if len(move_path) > 0:
                move_path.pop() 
            save_path_to_file(output_file, move_path)
            return True

        if is_board_empty(board):
            print("棋盘已清空，解决方案找到！")
            save_path_to_file(output_file, move_path)
            return True

        can_move_elements_forward = check_if_elements_can_move(board)
        if not can_move_elements_forward:
            print("没有可以移动的元素.")
            return False

        can_move_elements_inverse = reversed(can_move_elements_forward)

        for element, start_pos, end_pos, intersection, steps_to_intersection in can_move_elements_inverse:
            direction = calculate_move_direction(start_pos, intersection)
            is_column_movement = direction in ['up', 'down']

            board_copy = np.copy(board)
            if move_group_by_steps(board_copy, start_pos[0], start_pos[1], direction, steps_to_intersection, is_column=is_column_movement):
                eliminated, board_after_move = eliminate_elements_around(
                    board_copy, end_pos)

                if eliminated:
                    move_path.append(
                        (element, start_pos, direction, steps_to_intersection))
                    print(
                        f"元素 {element} 从 {start_pos} 向 {direction} 移动 {steps_to_intersection} 步")
                    print("移动后的棋盘:")
                    print(board_after_move)

                    eliminated_again, board_after_global_elimination, eliminated_coords = eliminate_same_elements(
                        board_after_move)

                    if eliminated_again:
                        move_path.append(
                            ('global_elimination', eliminated_coords))
                        print("执行额外的全局消除...")
                        print("消除的坐标:", eliminated_coords)
                        print(board_after_global_elimination)

                    if is_board_empty(board_after_global_elimination):
                        save_path_to_file(output_file, move_path)
                        return True

                    success = backtrack(
                        board_after_global_elimination, move_path.copy(), start_time, time_limit, result) 
                    if success:
                        return True

                    if time.time() - start_time > time_limit and len(move_path) > 0:
                        print("超时保存当前路径")
                        move_path.pop()
                        save_path_to_file(output_file, move_path)
                        return True

                    if eliminated_again:
                        move_path.pop()
                    move_path.pop()

        return False

    eliminated, board, eliminated_coords = eliminate_same_elements(board)
    if eliminated:
        move_path.append(('eliminate', eliminated_coords))
        result = backtrack(board, move_path, start_time, time_limit, result)
    else:
        result = backtrack(board, move_path, start_time, time_limit, result)

    if not result:
        print("解决方案未找到，没有移动路径可以保存。")

    return result

test_board_elimination_inverse()
